package com.test.daily.leetcode.y2022.m06.day0609.v05;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/9 下午 11:25
 * @version: 1.0
 */
public class Solution {
    public static int step1(int x, int y, int k, int a, int b) {
        return process(x, y, k, a, b);
    }
    public static int process(int x, int y, int k, int a, int b) {
        if (x < 0 || x > 8 || y < 0 || y > 9) {
            return 0;
        }
        if (k == 0) {
            return x == a && y == b ? 1 : 0;
        }
        int ways = 0;
        ways += process(x + 1, y + 2, k - 1, a, b);
        ways += process(x+ 1, y -2, k-1,a, b);
        ways += process(x- 1, y +2, k-1,a, b);
        ways += process(x- 1, y -2, k-1,a, b);
        ways += process(x+ 2, y -1, k-1,a, b);
        ways += process(x+ 2, y -1, k-1,a, b);
        ways += process(x- 2, y -1, k-1,a, b);
        ways += process(x- 2, y -1, k-1,a, b);
        return ways;
    }

    public static int step2(int x, int y, int k, int a, int b) {
        int[][][] dp = new int[x][y][k+1];
        dp[a][b][0] = 1;
        for(int i = 1; i <= k; i++){

            for(int j = 0; j < x; j++){
                for(int l = 0; l < y; l++){
                    int ways = 0;
                    ways += pick(dp, k - 1,j + 1, l + 2);
                    ways += pick(dp, k - 1,j+ 1, l -2);
                    ways += pick(dp,k - 1,j- 1, l +2);
                    ways += pick(dp, k - 1,j- 1, l -2);
                    ways += pick(dp,k - 1,j+ 2, l -1);
                    ways += pick(dp,k - 1,j+ 2, l -1);
                    ways += pick(dp,k - 1,j- 2, l -1);
                    ways += pick(dp, k - 1,j- 2, l -1);
                    dp[i][j][l] = ways;
                }
            }
        }
        return dp[k][0][0];
    }
    public static int pick(int[][][] dp, int i, int j, int k){
        return dp[i][j][k];
    }
}
